Attribute VB_Name = "BSearchModule"
'***************************************************************
' (c) Copyright 2000 Matthew J. Curland
'
' This file is from the CD-ROM accompanying the book:
' Advanced Visual Basic 6: Power Techniques for Everyday Programs
'   Author: Matthew Curland
'   Published by: Addison-Wesley, July 2000
'   ISBN: 0-201-70712-8
'   http://www.PowerVB.com
'
' You are entitled to license free distribution of any application
'   that uses this file if you own a copy of the book, or if you
'   have obtained the file from a source approved by the author. You
'   may redistribute this file only with express written permission
'   of the author.
'
' This file depends on:
'   References:
'     VBoostTypes6.olb (VBoost Object Types (6.0))
'     Compare.tlb (VBoost: Compare declaration for qsort and bsearch)
'   Files:
'     FunctionDelegator.bas
'   Minimal VBoost conditionals:
'     None
'   Conditional Compilation Values:
'     FUNCTIONDELEGATOR_NOHEAP = 1 'Minimize FunctionDelegator impact
'
' This file is discussed in Chapter 11.
'***************************************************************
Option Explicit
'Standard binary search routine.  Input data is similar to the QuickSort
'procedure, with the addition of pKeyData, which is a pointer to the data
'to be matched.
'The function returns -1 if no match is found, or the (0 based) index of the
'matching data element in the array.
Public Function BSearch(ByVal pKeyData As Long, ByVal pBase As Long, ByVal Number As Long, ByVal Size As Long, ByVal pfCompare As Long) As Long
Dim pLo As Long, pHi As Long, pMid As Long, pFound As Long
Dim Half As Long, Result As Long
Dim Compare As ICallCompare
Dim Delegator As FunctionDelegator
    'Set up the function pointer object
    Set Compare = InitDelegator(Delegator, pfCompare)
    
    'Initialize the search endpoints
    pLo = pBase
    pHi = pBase + (Number - 1) * Size
    'Execute the search
    Do While pLo <= pHi
        Half = Number \ 2
        If Half Then
            If Number And 1 Then
                pMid = pLo + Half * Size
            Else
                pMid = pLo + (Half - 1) * Size
            End If
            Result = Compare.Compare(pKeyData, pMid)
            If Result = 0 Then
                pFound = pMid
                Exit Do
            ElseIf Result < 0 Then
                pHi = pMid - Size
                If Number And 1 Then
                    Number = Half
                Else
                    Number = Half - 1
                End If
            Else
                pLo = pMid + Size
                Number = Half
            End If
        Else
            If Number Then
                If 0 = Compare.Compare(pKeyData, pLo) Then pFound = pLo
            End If
            Exit Do
        End If
    Loop
    If pFound Then
        BSearch = (pFound - pBase) \ Size
    Else
        BSearch = -1
    End If
    Set Compare = Nothing
End Function

